import java.util.*;

public class TSPTrace {
    static int n; // 城市数量
    static int[][] map; // 图的邻接矩阵
    static boolean[] vis; // 是否访问
    static int min = Integer.MAX_VALUE; // 最小花费
    static List<List<Integer>> allBest = new ArrayList<>(); // 所有最优路径

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入城市数量：");
        n = sc.nextInt();
        System.out.print("请输入道路数量：");
        int m = sc.nextInt();

        map = new int[n][n];
        for (int[] row : map) Arrays.fill(row, Integer.MAX_VALUE);

        System.out.println("请输入每条道路（格式：A B 10）：");
        for (int i = 0; i < m; i++) {
            String from = sc.next();
            String to = sc.next();
            int cost = sc.nextInt();
            int a = from.charAt(0) - 'A';
            int b = to.charAt(0) - 'A';
            map[a][b] = cost;
        }

        System.out.print("请输入起点城市（如 A）：");
        int start = sc.next().charAt(0) - 'A';

        vis = new boolean[n];
        min = Integer.MAX_VALUE;
        allBest.clear();

        List<Integer> path = new ArrayList<>();
        path.add(start);
        vis[start] = true;
        dfs(start, path, 0);

        System.out.println("\n最小花费是：" + min);
        System.out.println("最小花费共有" + allBest.size() + "种方案,分别是:");
        for (List<Integer> p : allBest) {
            for (int i : p) System.out.print((char)(i + 'A') + " ");
            System.out.println();
        }
    }

    static void dfs(int now, List<Integer> path, int cost) {
        if (path.size() == n) {
            int back = map[now][path.get(0)];
            if (back != Integer.MAX_VALUE) {
                int total = cost + back;

                // 打印回溯过程
                System.out.print("尝试路径：");
                for (int i : path) System.out.print((char)(i + 'A') + " ");
                System.out.print((char)(path.get(0) + 'A'));
                System.out.println(" -> 总花费：" + total);

                if (total < min) {
                    min = total;
                    allBest.clear();
                    allBest.add(new ArrayList<>(path));
                } else if (total == min) {
                    allBest.add(new ArrayList<>(path));
                }
            }
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!vis[i] && map[now][i] != Integer.MAX_VALUE) {
                vis[i] = true;
                path.add(i);
                dfs(i, path, cost + map[now][i]);
                path.remove(path.size() - 1);
                vis[i] = false;
            }
        }
    }
}
